"""
https://leetcode.cn/problems/search-a-2d-matrix-ii/description/

240. 搜索二维矩阵 II
已解答
中等
相关标签
相关企业
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
 

示例 1：


输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：


输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

"""
from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        """
        思想还是二分查找

        按照题目所述，规律如下：
        如果a<m,b<n，则必定有matrix[a][b]<matrix[m][n]

        """
        width=len(matrix)
        height=len(matrix[0])

        min_row,min_col,max_row,max_col=0,0,height-1,width-1
        if matrix[min_row][min_col]>target:
            return False
        if matrix[max_row][max_col]<target:
            return False
        
        while min_row<max_row and min_col<max_col:
            mid_row=(min_row+max_row)//2
            mid_col=(min_col+max_col)//2

            if matrix[mid_row][mid_col]==target:
                return True
            elif matrix[mid_row][mid_col]>target:
                pass


            pass



        pass

if __name__=='__main__':
    # TODO 240. 搜索二维矩阵 II
    pass

